#  03.02. 栈的最小值
#
#from array import array  
#怎么用list 做出效果比array还好了，垃圾
class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = [] #array('l')
        self.min_stack = [] #array('l')

    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.min_stack) == 0 :
            self.min_stack.append(x)
        elif x <= self.getMin() :
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.getMin():
            self.min_stack.pop()

    def top(self) -> int:
        if len(self.stack) != 0:
            tmp = self.stack.pop()
            self.stack.append(tmp)
        return tmp

    def getMin(self) -> int:
        tmp = self.min_stack.pop()
        self.min_stack.append(tmp)
        return tmp



'''
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返 回栈中最小元素的操作。 
【要求】     1．pop、push、getMin操作的时间复杂度都是O(1)。 
            2．设计的栈类型可以使用现成的栈结构。
'''

class getmin_stack1:
    def __init__(self) -> None:
        self._stackdata = []
        self._stackmin = []
    def getmin(self) -> object:
        if not self._stackmin : raise Exception('Your stack is empty.')
        tmp = self._stackmin.pop()
        self._stackmin.append(tmp)
        return tmp
    def push(self, new_num: object):
        if len(self._stackmin) == 0:
            self._stackmin.append(new_num) # 压入最小栈
        elif new_num <= self.getmin():  # 当新元素比最小栈小才压入
            self._stackmin.append(new_num)
        self._stackdata.append(new_num)
    def pop(self) -> object:
        if not self._stackdata: raise Exception('Your stack is empty.')
        value = self._stackdata.pop()
        if value == self.getmin():
            self._stackmin.pop()
        return value

class getmin_stack2:
    def __init__(self) -> None:
        self._stackdata = []
        self._stackmin = []
    def getmin(self) -> object:
        if not self._stackmin : raise Exception('Your stack is empty.')
        tmp = self._stackmin.pop()
        self._stackmin.append(tmp)
        return tmp
    def push(self, new_num: object):
        if len(self._stackmin) == 0:
            self._stackmin.append(new_num) # 压入最小栈
        elif new_num < self.getmin():  # 当新元素比最小栈小才压入
            self._stackmin.append(new_num)
        else : self._stackmin.append(self.getmin())     
        self._stackdata.append(new_num)
    def pop(self) -> object:
        if not self._stackdata: raise Exception('Your stack is empty.')
        self._stackmin.pop()
        return self._stackdata.pop()



a = getmin_stack2()
a.push(3)
print(a.getmin())
a.push(4)
print(a.getmin())
a.push(1)
print(a.getmin())
a.pop()
print(a.getmin())